package base.Chapter00_Structures.C07_Tree.BinaryFindTree;

/**
 * 二叉查找树
 * <p>
 * 功能列表：
 * 1，查找
 * 2，插入
 * 3，删除
 * 4，遍历
 */
public class BinaryFindTree {
    private Node root;

    /**
     * 查找指定元素
     * 逻辑：
     * 去当前节点的nodeData属性比较
     * 情况1：nodeData==data 返回该节点
     * 情况2：nodeData>data  查找当前node的左子节点（因为左边小）
     * 情况3：nodeData<data  查找当前node的右子节点（因为右边大）
     *
     * @param data 目标值
     * @return 找到返回Node， 找不到返回null
     */
    public Node find(int data) {
        Node node = root;
        while (node != null) {
            if (node.getData() == data)
                return node;
            else if (node.getData() > data)
                node = node.getLeft();
            else
                node = node.getRight();
        }
        return null;
    }

    // 用递归实现
    // 递归实现一般都是有一个启动函数+一个递归函数
    // 因为初始值需要在启动函数中设置
    public Node findWithRecursion(int data) {
        return findWithRecursion(data, root);
    }

    private Node findWithRecursion(int data, Node node) {
        if (node == null)//递归终止条件等价于非递归的循环控制条件
            return null;

        if (node.getData() == data)
            return node;
        else if (node.getData() > data)
            return findWithRecursion(data, node.getLeft());
        else
            return findWithRecursion(data, node.getRight());
    }

    /**
     * 插入元素
     */

    public void insert() {
        //TODO
    }
}
